/*
 * @lc app=leetcode.cn id=188 lang=swift
 *
 * [188] 买卖股票的最佳时机 IV
 */

// @lc code=start
class Solution188 {
    // 最多可以完成k笔交易，一共有(2k + 1)中状态
    // dp[i][0] 表示没有任何的操作
    // dp[i][1] 表示第一次买入
    // dp[i][2k - 1] 表示第k次买入
    // dp[i][2k] 表示第k次卖出
    func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
        guard prices.count > 0 else {
            return 0
        }
        guard k > 0 else {
            return 0
        }
        var dp = Array(repeating: Array(repeating: 0, count: 2 * k + 1), count: prices.count)
        // 初始化
        for j in 0...2 * k {
            if j % 2 == 0 {
                dp[0][j] = 0
            }
            if j % 2 == 1 {
                dp[0][j] = -prices[0]
            }
        }
        // 递推
        for i in 1..<prices.count {
            for j in 1...(2 * k) {
                // 卖出
                if j % 2 == 0 {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])
                }
                // 买入
                if j % 2 == 1 {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i])
                }
            }
        }
        return dp[prices.count - 1][2 * k]
    }
    // 上面的代码做个调整
    func maxProfit2(_ k: Int, _ prices: [Int]) -> Int {
        if prices.count == 0 {
            return 0
        }
        var dp = Array(repeating: Array(repeating: 0, count: 2 * k + 1), count: prices.count)
        for i in 0..<prices.count {
            for j in 0...(2 * k) {
                // 初始化
                if i == 0 {
                    if j % 2 == 0 {
                        dp[0][j] = 0
                    } else {
                        dp[0][j] = -prices[0]
                    }
                    continue
                }
                if j == 0 {
                    dp[i][j] = dp[i - 1][j]
                    continue
                }
                if j % 2 == 1 {
                    // 存在存货
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i])
                } else {
                    // 不存在存货
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])
                }
            }
        }
        return dp[prices.count - 1][2 * k]
    }
    
    static func test() {
        let prices = [2,4,1]
        let res = Solution188().maxProfit(0, prices)
        print(res)
    }
}
// @lc code=end

